\documentclass{article}

\author{Tom Shortell, Mike DeLaurentis, James Rogers}

\begin{document}
\title{CS 543 Fall 2011 Assignment 2}
\maketitle
\section{Implementation details}

\subsection{I}

\subsubsection{creat and open}
The \textit{creat} and \textit{open} system calls are merged together internally since the only difference is a flag for whether the file is to be created if it doesn't exist. 
The \textit{handleCreatOpen} function was created to implement these function calls from the main syscall handler in \textit{UserProcess.java}. 
The function goes directly into the kernel filesystem to open the file. 
The function call makes attempts to bullet-proof against a bad virtual address using the \textit{validVirtualAddress} function inside of \textit{UserProcess.java}.
It also checks against a failed file open.
Currently, the files are not memory mapped into the main memory - this wasn't a requirement in the instructions (assuming it is part of another assignment since not all system calls where not required to be implemented).
Also to be noted, there is not a system wide file table because it is assumed that the stub file system is doing this. 
Also, since it is reading sequential, multiple processes can't share the same OpenFile structure. 

\subsubsection{read and write}
The \textit{read} and \textit{write} system calls are implemented in a similar fashion as \textit{creat} and \textit{open}. 
Both system calls are checking for a valid file descriptor and against the virtual memory. 
These calls also check the correctness of the individual virtual memory accesses and attempt to prevent any kernel exceptions. 

\subsubsection{close and unlink}
The \textit{close} and \textit{unlink} system call are implemented like the previous system calls (\textit{handleClose} and \textit{handleUnlink}, respectively). 
The \textit{close} system call simply closes the OpenFile object locally (which is handled in StubFileSystem) and the local file descriptor is freed for further use. 
The \textit{unlink} system call uses the string provided and the StubFileSystem to remove the file. 

\subsubsection{bulletproofing}
The system calls were targeted for bullet proofing and each argument is checked for errors. 
Virtual memory addresses are checked for validity against logical address space. 
Errors immediately terminate the process using a \textit{terminateProcess} in \textit{UserProcess.java}. 
\textit{terminateProcess} immediately unloads any sections that are being used. 
It then sets an exit status (usually -1) and finishing the thread.

\subsubsection{halt system call}
The halt system call has been checked against the assigned process ids (pid) and if the pid is not 0 it will ignore the halt system as specified. 
When the pid is 0, the machine halts correctly.

\subsubsection{Error Conditions}
Error conditions follow the \textit{syscall.h} definitions for each of the implemented syscalls.

\subsubsection{File Descriptors}
The file descriptors are setup in Vector of \textit{OpenFile}. 
A LinkedList is kept of the available files so there can be reuse of the individual descriptors. 
An artificial limit of 32 was created (bigger then 16) and this is per process (StubFileSystem appears to stop at 16 though).
stdin and stdout are opened when the \textit{UserProcess} constructor is called and it also allocates the space of the Vector and sets up the linked list of available file descriptors. 
Both are created using the console from the \textit{UserKernel}.

Another note of an issue with the \textit{StubFileSystem} and the original \textit{UserProcess} code is that the level of 16 open files hinders progress. 
Code was added to clean up executable open files that the original code wasn't cleaning up. 
Without this, the nachos sh program would not open another file at the 16th available program. 
The code change keeps the file reference locally in \textit{UserProcess} and cleans it up at \textit{terminateProcess}. 
This was designed this way for future use in case a more complex paging algorithm is designed when a real filesystem and disk are included in the system. 

\subsection{II}

\subsubsection{Physical Memory Allocation}
The physical memory was allocated into blocks based on the assignment details. 
There was no capability for page preemption or faulting (no backing store). 
This was also simplified by having no dynamic memory requirements (no malloc equivalent). 
The \textit{UserKernel.java} was modified to control the entire linked list of free pages (at startup all pages are free). 
This is based on the suggestion from the assignment instructions. 
The synchronization is provided by enabling and disabling of interrupts. 
The \textit{UserProcess.java} was modified to use the two provided functions \textit{getNextPage} and \textit{freePage}. 
These functions provide the ability to use any available frame in physical memory. 
At startup however, it will allocate contiguously until it recycles through the list, then it becomes a FIFO queue in theory. 

\subsubsection{Virtual Memory Updates}
The virtual memory access functions where modified to re-use the pageTable that was already provided. 
The \textit{readVirtualMemory} and \textit{writeVirtualMemory} have been modified to use the Processor to determine the virtual memory address to physical addresses. 
Both function calls handle any error cases and will copy the data to/from like the previous design did.
Each function will terminate the process (using \textit{terminateProcess}) if a segfault occurs. 

\subsubsection{loadSections and unloadSections}
The \textit{loadSections} and \textit{unloadSections} have been modified to allow the handling of pages in different places. 
\textit{loadSections} now properly loads each page from the Coff executable very similar to the original code, except the physical page location is dynamic. 
Code was also added to allocate the stack and arguments pages that were being ``done'' in the \textit{load} function. 
\textit{unloadSections} was completely implemented to clear physical pages and is called via \textit{terminateProcess} and \textit{loadSections} (when it runs out of pages while loading).

\subsubsection{Final Note}
The first code attempt used \textit{UserProcess.newUserProcess} to create new processes (children). 
On the 15th attempt in a shell, the nachos security manager would throw an RuntimePermission exception. 
This didn't make a lot of sense since the previous code only retrieved the file; not sure why it tried to start running the class. 
Regardless, this was fixed by calling \textit{UserProcess} constructor directly. 

\subsection{III}

\subsubsection{exec}
This syscall actually created the capability to do multiprogramming. 
The syscall was implemented via the \textit{handleExec} function in \textit{UserProcess.java}.
It handles the arguments (filename of the process) and error checking. 
If there are no errors, the call creates another \textit{UserProcess} and calls \textit{execute} to get it started. 
The processing also adds to a HashMap that allows a parent process to keep track of its child processes and helps properly implement the join process.
The constructor was modified to allow the creation of this HashMap.

This method of creating the processes effectively separates the child from the parent, except that the parent knows the child's process id for joining. 
The state, status, and file descriptors are all different between the parent and child. 

\subsubsection{join}
This syscall was implemented in \textit{handleJoin} function call in \textit{UserProcess.java}.
It will use \textit{KThread.join()} of the child thread to wait on its completion. 
The processing of \textit{handleJoin} checks that the pid is one of the children of the parent. 
The pids are allocated during the creation of the UserProcess via a static global counter. 
There is a minor issue here in that the UserProcess class does not recycle the pids; which was not required for this assignment. 
This number is an integer so it will be relatively hard to overflow this number. 
Join also verifies the exit status from the child process if available. 

\subsubsection{exit}
Exit was implemented via \textit{handleExit}. 
Its implementation was very simple, it takes the status argument and runs \textit{terminateProcess} to clean up. 
If the process was the root process, however, it will terminate the machine. 

\subsubsection{exit statuses}
The exit statuses are setup to be chosen when \textit{terminateProcess} is called. 
\textit{-1} is the key number for kernel termination. 
The user processes can use this number to get abnormal termination - similar to unix and it is a design decision that I personally like so implemented it this way. 

\subsection{IV - Lottery Scheduling}

\subsubsection{Refactoring common functionality}

In order to implement lottery scheduling, we refactored the work we had done for the priority scheduling in project 1. We created an abstract base class called nachos.threads.BasePriorityScheduler, which has two inner classes: PriorityQueue and ThreadState. This base class provides some common methods that would be needed by a class that implements scheduling where threads are released based on some kind of priority: functions for getting priority and effective priority and setting priority for a given KThread, and for incrementally increasing and decreasing priority.

The ThreadState inner class defines the following properties:

\begin{description}
\item [thread] The KThread that this ThreadState refers to.
\item [priority] The priority of the thread.
\item [effectivePriority] The current effective priority of the thread.
\item [waitQueue] The queue on which the thread is currently waiting,
  or null if the thread is not waiting on a thread.
\item [ownedQueues] A set of queues that the thread currently owns.
\end{description}

In addition to getters and setters, ThreadState defines the following methods:

\begin{description}
\item [waitForAccess] Takes a PriorityQueue, sets it as this thread's
  waitQueue, removes it from the list of queues owned by this thread,
  and recalculates effective priority (since this thread may have lost
  ownership of a queue).
\item [acquire] Takes a PriorityQueue and adds it to the set of
  queues owned by this thread.
\item [setPriority] (abstract) Subclasses implement this to set the priority of the thread.
\item [calculateEffectivePriority] Subclasses implement this with the
  logic for calculating effective priority.
\end{description}

The PriorityQueue inner class defines only two properties: a ThreadState indicating which thread currently owns the queue, and a boolean transferPriority which indicates whether it transfers priority from waiting threads to its owner. It defines these methods:

\begin{description}
\item [acquire] Simply finds the ThreadState for the thread it is given and calls its acquire method to let it know that it now has ownership of the queue.
\item [waitForAccess] If the given thread currently owns the queue, breaks the ownership. then adds it to my list of waiting threads and calls waitForAccess on the ThreadState.
\item [nextThread] Clears out the existing owner and recalculates its new effective priority, then pops a thread off the queue, lets it acquire this queue, and returns it.
\item [pop] (abstract) Subclasses need to implement this to remove a thread from the waiting list.
\item [addThread] (abstract) Subclasses need to implement this to add a thread to the queue.
\end{description}

\subsubsection{Changes to PriorityScheduler}

We had to make a few changes to PriorityScheduler in order to refactor the common functionality into the base class and then make it extend the base class.

\subsubsection{LotteryScheduler}

\paragraph{LotteryScheduler.ThreadState}

The ThreadState class within LotteryScheduler implements setPriority simply by setting the priority and then recalculating effective priority. It implements calculateEffectivePriority by setting effectivePriority to the sum of the total number of tickets on all queues owned by this thread, plus its own priority.

\paragraph{LotteryScheduler.PriorityQueue}

Each LotteryScheduler.PriorityQueue keeps a set of the threads that are currently waiting. It has a getTotalTickets method which returns the total number of tickets held by all waiting threads, which is simply the sum of the effective priorities of all waiting threads. To pop a thread off the queue, it simply chooses a random number $k$ between 0 and the total number of tickets. It then iterates over the threads, keeping a tally of how many tickets it has seen from the threads so far. As soon as it has seen more than $k$ tickets, it chooses the thread it is currently on. This makes it so that the probability of a thread $t_i$ being chosen is $\frac{tickets(t_i)}{\sum_{j=0}^n tickets(t_j)}$ where $tickets(t_i)$ is the number of tickets owned by thread $i$ and $n$ is the total number of threads.

Note that we simply model the tickets held by a thread as a number, so there is no cost for having more tickets. The cost of the operations on the LotteryScheduler is only dependant on the number of threads in the queue.

\section{Running}

The modified files in thread package are:
\begin{itemize}
\item ThreadedKernel.java
\item PriorityScheduler.java
\item LotteryScheduler.java
\item BasePriorityScheduler.java
\end{itemize}

The modified files in the userprog package are:
\begin{itemize}
\item UserKernel.java
\item UserProcess.java
\end{itemize}

To run the program, it is simple to have the files in the normal
nachos distribution plus the ones above in the threads package.  First
go to the proj2 directory, then simply type \textit{gmake} [enter],
and then \textit{../bin/nachos} [enter].  A few self tests run,
required to press \textit{q} to exit the console test, then the nachos
shell runs from the test directory.  By definition, someone can use
\textit{-x programname} to run something different then
\textit{sh.coff} at the command line.




\end{document}
